Modern packet communication networks are commonly configured to carry multiple different types of communication traffic and applications, with different service requirements. These requirements may be expressed in quantitative or statistical terms, based on characteristics such as throughput, delay, jitter, packet loss, or other measures of priority. Network users typically enter into agreements with network service providers that specify the level of service the users are to receive, expressed in terms of these sorts of differentiating service characteristics. The service provider must program the nodes in the network so that they can determine how to treat each packet they receive and forward, depending on the applicable service characteristics.
Various service differentiation schemes are known in the art. Most of these schemes are based on tagging packets (also known as “marking” or “labeling” packets) to indicate their class of service, priority and/or other traffic handling characteristics. An exemplary service differentiation scheme is described by Blake et al., in “An Architecture for Differentiated Services,” published by the Internet Engineering Task Force (IETF) Network Working Group as Request for Comments (RFC) 2475 (1998), which is incorporated herein by reference. This and other IETF documents cited herein are available at www.ietf.org. The nodes in a given network service domain decide whether to forward, delay or drop each packet they receive depending on the tags carried by the packets and the availability of network resources to process and forward the packets. The terms “tag” and “tagging” as used in the present patent application and in the claims should be understood as referring to any addition or modification of a predetermined field in data packets transmitted through a network for purposes of service differentiation and traffic handling.
One characteristic according to which services are commonly differentiated is their allocation of bandwidth, which may be guaranteed or opportunistic. At any point in time, resources that are not being used by guaranteed service components may be used by opportunistic components. Services with mixed guaranteed and opportunistic bandwidth components may also be available. The most popular services can be grouped in the following categories:                Guaranteed, fixed bandwidth (GF): This service does not have any opportunistic component, and the network must ensure timely delivery of all packets that comply with the service bandwidth.        Guaranteed with excess (GE): This service includes a guaranteed component, usually known in the art as its Committed Information Rate (CIR), and an excess component, known as Excess Information Rate (EIR). The network must deliver all packets that comply with the CIR and make its best efforts to deliver the excess traffic.        Best Efforts (BE): This is a service that has only an opportunistic component. The network will make its best efforts to deliver the packets, but no guarantees are made.        
In communication networks that are based on statistical multiplexing techniques, such as Internet Protocol (IP) and Frame Relay networks, optimal utilization of network resources can be achieved by shifting them dynamically between users. Thus, the opportunistic services noted above take advantage of free resources available during periods of low guaranteed service traffic. Another common practice is to overbook network resources, by provisioning more services than the network can actually handle. Overbooking is commonly used for opportunistic service components. During times when the network is not congested (low utilization), the opportunistic services can use their full provisioned bandwidth. When the network is congested, the opportunistic services use whatever bandwidth is left over from guaranteed services. The overbooking ratio is defined as the ratio of the total provisioned bandwidth for BE and excess traffic to the total available bandwidth for these services.
When overbooking is used, and the available bandwidth for opportunistic traffic is less than the total provisioned, the available bandwidth is preferably fairly distributed among the services. The fair distribution may be an equal distribution among the services, or a weighted distribution. For example, excess traffic from guaranteed services may receive a higher weight than pure BE traffic. One such scheme for allocating excess bandwidth is defined by Seddigh et al., in an IETF Internet Draft entitled “An Assured Rate Per-Domain Behavior for Differentiated Services” (draft-ietf-diffserv-pdb-ar-01.txt, July, 2001), which is incorporated herein by reference.
Overbooking may also be applied to guaranteed services, creating a situation in which the sum of the CIRs allocated to all the guaranteed services exceeds an Aggregate CIR Limit (ACL). In other words:ΣCIR(guaranteed services)=ACL×Overbooking.Although overbooking guaranteed services may appear to contradict the nature of such services, the statistical behavior of the network connections allows service providers to work in this way and thus to make more cost-effective use of available network resources. The actual resources of the network are typically assigned in accordance with the ACL only.